#include <cstdlib>
#include <iostream>
#include <time.h>
#include <sys/time.h>
#include <sys/resource.h>

#include <string>
#include <Graph.h>

// #define NDEBUG
#include <assert.h>

#ifdef _COMBSOLV_
#include "../combsolvers/StabSolvers.h"
#include "../combsolvers/MCR.h"
string 	errorstr = "Please specify combinatorial algorithm, graph file in the DIMACS format and number of threads.\n<execname> <algorithm> <graph-file>\n";
int nargs = 4;
#endif

#ifdef _IPSOLV_
#include "../ipsolvers/FracSolvers.h"
#include "../lagsolvers/LagSolvers.h"
string errorstr = "Please, specify formulation, relaxation, graph file in the DIMACS format, and max number of stable sets.\nmain <form> <relax> <graph-file> <k>\n";
int nargs = 5;
#endif

using namespace std;

// vertex order
static int *		Rperm;
static int rcmp(const void *a, const void *b) {
	return Rperm[*((int *)b)] - Rperm[*((int *)a)];
}

int main (int argc, char *argv[]) {
	if (argc < 2) {
		cout << errorstr;
		return 0;
	}

	int arg = 1;

	string formstr;
	formstr.assign(argv[arg++]);

#ifdef _IPSOLV_
	if (formstr == "color" || formstr == "acolor" || formstr == "fraccolor")
		nargs--;
#endif

	if (argc < nargs) {
		cout << errorstr;
		return 0;
	}

#ifdef _IPSOLV_
	string relaxstr;
	relaxstr.assign(argv[arg++]);
#endif

	FILE * graphFile = fopen(argv[arg], "r");
	if (!graphFile) {
		printf("Could not open %s.\n", argv[arg]);
		return 0;
	}

	string filestr;
	filestr.assign(argv[arg++]);
	size_t found = filestr.rfind(".clq");

	GraphFactory<Graph> * fact = new GraphFactory<Graph>();

	Graph * g;
	if (found != string::npos)
		g = Graphs::readDimacsGraph<Graph>(graphFile, GT_COMPLEMENT, fact);
	else
		g = Graphs::readDimacsGraph<Graph>(graphFile, GT_GRAPH, fact);
	delete fact;

	Graph * gh;
	if (!g) {
		fclose(graphFile);
		printf("Could not read graph file %s.", argv[3]);
		return 0;
	}
	fclose(graphFile);

	printf("number of vertices: %d,  and edges: %lld\n", g->nverts(), g->nedges());

#ifdef _IPSOLV_
	int k;
	if (formstr == "color" || formstr == "acolor" || formstr == "fraccolor")
		k = 0;
	else
		k = atoi(argv[arg]);
#else
	int k = 1;
#endif

	struct timespec start, end;
	double elapsed;
    struct timeval tv;
    gettimeofday(&tv, NULL);
    start.tv_sec = tv.tv_sec;
    start.tv_nsec = tv.tv_usec * 1000;

	int m = g->nedges() >> 1;

	// vertex order
	int n = g->nverts();
	int R[n];
	int rep;
	for (rep = 0; rep < n; rep++)
		R[rep] = rep;

	{
		int err;
		if (formstr != "color" && formstr != "acolor") {
			Graph * gc = g->complement();
			int antideg[gc->nverts()];
			int surplus;
			err = gc->adjSizes(antideg);
			if (err) {
				printf("Error %d determining anti-neighborhoods.", err);
				exit(0);
			}
			delete gc;

			int j = 0, l = 0;
			for (rep = 0; rep < n; j+=antideg[rep],rep++)
				if (n-antideg[rep]-1 >= k) {
					R[l] = rep;
					antideg[l++] = antideg[rep];
				}
			if (l < n)
				n = l;
			gh = g->homomorphism(n, R);
			printf("Number of vertices retained: %d\n", n);
			fflush(NULL);
		}
		else
			gh = g;

		int rank[n];
		err = Graphs::mcrDegreeSort(gh, rank);
		assert(!err);

		Rperm = rank;
		qsort(R, n, sizeof(int), rcmp);
		if (gh != g)
			delete gh;
		gh = g->homomorphism(n, R);
	}

	StabSolver * solver = NULL;
#ifdef _IPSOLV_
	if (formstr == "stab") {
		solver = StabSolver::create<StabModeler,Graph>(gh, new ModelerFactory<StabModeler,Graph>());
	}
	else if (formstr == "rep" || formstr == "color") {
		if (relaxstr == "linear") {
			solver = MaxRepStab::create<RepModeler,Graph>(relaxstr, gh, new ModelerFactory<RepModeler,Graph>(), k);
		}
		else if (relaxstr == "alinear") {
			solver = MaxRepStab::create<ARepModeler,Graph>(relaxstr, gh, new ModelerFactory<ARepModeler,Graph>(), k);
		}
		else if (relaxstr == "lag") {
			solver = MaxRepLag::create<RepModeler,Graph>(relaxstr, gh, new ModelerFactory<RepModeler,Graph>(), k);
		}
		else if (relaxstr == "alag") {
			solver = MaxRepLag::create<ARepModeler,Graph>(relaxstr, gh, new ModelerFactory<ARepModeler,Graph>(), k);
		}
	}
	else if (formstr == "fracrep" || formstr == "fraccolor") {
		solver = FracColor::create<ARepModeler,Graph>(relaxstr, gh, new ModelerFactory<ARepModeler,Graph>(), k);
	}
#endif

#ifdef _COMBSOLV_
	int nt = atoi(argv[arg]);
	printf("number of threads:%d \n", nt);
	fflush(NULL);
	solver = MCRStabSolver::create(formstr,nt, g);
#endif

	if (!solver) {
		printf("Error in creating solver.\n");
		delete gh;
		delete g;
		exit(0);
	}
	if (solver->solveByEnumeration()) {
		printf("Error in enumeration.\n");
		exit(0);
	}

	gettimeofday(&tv, NULL);
	end.tv_sec = tv.tv_sec;
	end.tv_nsec = tv.tv_usec * 1000;

	elapsed = (end.tv_sec - start.tv_sec);
	elapsed += (end.tv_nsec - start.tv_nsec) / 1000000000.0;

	double bs;
	solver->getBest(&bs);
	printf("Largest size found: %d\n", (int) bs);

	int nnodes;
	solver->getNodes(&nnodes);
	printf("Number of explored nodes: %d\n", nnodes);

	printf("Elapsed time: %8.5g second(s).\n", elapsed);

	struct rusage relapsed;
	getrusage(RUSAGE_SELF,&relapsed);
	printf("Detailed total time: user time = %ld.%ld second(s); system time = %ld.%ld second(s).\n", relapsed.ru_utime.tv_sec,relapsed.ru_utime.tv_usec, relapsed.ru_stime.tv_sec, relapsed.ru_stime.tv_usec);

	delete gh;
	delete g;
	delete solver;

	return 0;
}
